An Analysis of Rule Coverage as a Criterion in Generating\ud Minimal Test Suites for GrammarBased\ud Software

摘要

The term grammar-based software describes software whose\udinput can be specified by a context-free grammar. This\udgrammar may occur explicitly in the software, in the form\udof an input specification to a parser generator, or implicitly,\udin the form of a hand-written parser, or other inputverification\udroutines. Grammar-based software includes not\udonly programming language compilers, but also tools for\udprogram analysis, reverse engineering, software metrics and\uddocumentation generation. Such tools often play a crucial\udrole in automated software development, and ensuring their\udcompleteness and correctness is a vital prerequisite for their\uduse.\udIn this paper we propose a strategy for the construction\udof test suites for grammar based software, and illustrate this\udstrategy using the ISO C++ grammar. We use the concept of\udrule coverage as a pivot for the reduction of implementationbased\udand specification-based test suites, and demonstrate\uda significant decrease in the size of these suites. To demonstrate\udthe validity of the approach, we use the reduced test\udsuite to analyze three grammar-based tools for C++. We\udcompare the effectiveness of the reduced test suite with the\udoriginal suite in terms of code coverage and fault detection.